home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / graphics / ch_hull.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  1.9 KB  |  128 lines
  1. #include <LEDA/plane.h>
  2. #include <LEDA/window.h>
  3.  
  4. window W;
  5.  
  6. list<point> C_HULL(list<point> L)
  7. { 
  8.   if (L.length() < 3) return L;
  9.  
  10.   list<point> CH;
  11.   list_item last;
  12.   point p;
  13.  
  14.   L.sort();  // sort points lexicographically
  15.  
  16.  
  17.   // initialize convex hull with first two points
  18.  
  19.   p = L.pop();
  20.   CH.append(p);
  21.   while (L.head() == p) L.pop();
  22.   last = CH.append(L.pop());
  23.  
  24.  
  25.   // scan remaining points
  26.  
  27.   forall(p,L)
  28.   {
  29.     if (p == CH[last]) continue;  // multiple point
  30.  
  31.     // compute upper tangent (p,up)
  32.  
  33.     list_item up = last;
  34.     list_item it = CH.cyclic_succ(up);
  35.  
  36.     while (left_turn(CH[it],CH[up],p))
  37.     { up = it;
  38.       it = CH.cyclic_succ(up);
  39.      }
  40.  
  41.  
  42.     // compute lower tangent (p,low)
  43.  
  44.     list_item low = last;
  45.     it = CH.cyclic_pred(low);
  46.  
  47.     while (right_turn(CH[it],CH[low],p))
  48.     { low = it;
  49.       it = CH.cyclic_pred(low);
  50.      }
  51.  
  52.  
  53.     // remove all points between up and low
  54.  
  55.     if (up != low)
  56.     { it = CH.cyclic_succ(low);
  57.  
  58.       while (it != up)
  59.       { CH.del(it);
  60.         it = CH.cyclic_succ(low);
  61.        }
  62.      }
  63.  
  64.     // insert new point
  65.  
  66.     last = CH.insert(p,low);
  67.  
  68.    }
  69.  
  70.   return CH;
  71. }
  72.      
  73.  
  74.  
  75. main()
  76. {
  77.   //window W;
  78.   W.init(-100,100,-100);
  79.   W.set_node_width(5);
  80.  
  81.   int N = 500;
  82.  
  83.   panel P("convex hull");
  84.  
  85.   P.int_item("# points",N,1,2000);
  86.   int b1 = P.button("mouse");
  87.   int b2 = P.button("random");
  88.   int b3 = P.button("quit");
  89.  
  90.   for(;;)
  91.   { 
  92.     list<point> L;
  93.     point p,q;
  94.  
  95.     int but = P.open();
  96.  
  97.     W.clear();
  98.  
  99.     if (but == b1)
  100.       while (W >> p)
  101.       { W.draw_point(p,blue);
  102.         L.append(p);
  103.        }
  104.  
  105.     if (but == b2)
  106.       for(int i = 0; i<N; i++) 
  107.       { point p(random(-90,90),random(-90,90));
  108.         W.draw_point(p,blue);
  109.         L.append(p);
  110.        }
  111.  
  112.     if (but == b3) break;
  113.   
  114.     list<point> C = C_HULL(L);
  115.   
  116.     p = C.tail();
  117.   
  118.     forall(q,C) 
  119.     { W.draw_segment(p,q,violet);
  120.       W.draw_filled_node(q,violet);
  121.       p = q;
  122.      }
  123.   }
  124.    
  125.  return 0;
  126. }
  127.  
  128.